import java.util.HashMap;
import java.util.Map;

public class majorityElement {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        Map<Integer, Integer> m = new HashMap<>();
        for(int c : nums){
            if(m.containsKey(c)){
                m.put(c, m.get(c) + 1);
                if(m.get(c) > n/2){
                    return c;
                }
            }else{
                m.put(c, 1);
            }
        }
        return -1;
    }

    public int majorityElement2(int[] nums) {
        // 摩尔投票
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }

}
